#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*, unsigned int>> q;
        q.push_back({ root,1 });
        unsigned int ret = 0;
        while (q.size())
        {
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(y2 - y1 + 1, ret);

            vector<pair<TreeNode*, unsigned int>> tmp;
            for (auto& [x, y] : q)
            {
                if (x->left) tmp.push_back({ x->left,2 * y });
                if (x->right) tmp.push_back({ x->right,2 * y + 1 });
            }
            q = tmp;
        }
        return ret;
    }

    void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& visited)
    {
        visited[i][j] = true;
        int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        for (auto dic : dics)
        {
            int x = i + dic[0], y = j + dic[1];
            if (x >= 0 && x < heights.size() && y >= 0 && y < heights[0].size() && !visited[x][y] && heights[x][y] >= heights[i][j])
            {
                dfs(heights, x, y, visited);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<bool>> Pac(m, vector<bool>(n));
        vector<vector<bool>> Atl(m, vector<bool>(n));

        for (int i = 0; i < m; ++i) dfs(heights, i, 0, Pac);
        for (int i = 0; i < n; ++i) dfs(heights, 0, i, Pac);

        for (int i = 0; i < m; ++i) dfs(heights, i, n - 1, Atl);
        for (int i = 0; i < n; ++i) dfs(heights, m - 1, i, Atl);
        vector<vector<int>> ret;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (Pac[i][j] && Atl[i][j])
                    ret.push_back({ i,j });
            }
        }
        return ret;
    }

    int dics[8][2] = { {0,1},{0,-1},{1,0},{-1,0},{-1,1},{-1,-1},{1,1},{1,-1} };
    bool visited[50][50] = { 0 };
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        int count = 0;
        for (auto dic : dics)
        {
            int x = dic[0] + i, y = dic[1] + j;
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'M')
            {
                ++count;
            }
        }
        if (count == 0)
        {
            board[i][j] = 'B';
            for (auto dic : dics)
            {
                int x = dic[0] + i, y = dic[1] + j;
                if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
        else
        {
            board[i][j] = count + '0';
            return;
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M')
        {
            board[x][y] = 'X';
            return board;
        }
        int m = board.size(), n = board[0].size();
        dfs(board, x, y);
        return board;
    }

    vector<pair<int, int>> v;
    bool check(long long mid)
    {
        int ans = v[0].first;
        for (int i = 1; i < v.size(); ++i)
        {
            if (v[i].second < ans + mid) return false;
            if (v[i].first > ans + mid) ans = v[i].first;
            else ans = ans + mid;
        }
        return true;
    }

    int maxPossibleScore(vector<int>& start, int d) {
        for (int i = 0; i < start.size(); ++i)
        {
            v.push_back({ start[i],start[i] + d });
        }
        sort(v.begin(), v.end());

        long long left = 0, right = 2e9 + 1;
        while (left < right)
        {
            long long mid = (left + right + 1) >> 1;
            if (check(mid)) left = mid;
            else right = mid - 1;
        }
        return left;
    }

    int memo[101];
    int fib(int n) {
        memset(memo, -1, sizeof(memo));
        return dfs(n);
    }

    int dfs(int n)
    {
        if (memo[n] != -1)
        {
            return memo[n];
        }

        if (n == 0 || n == 1)
        {
            memo[n] = n;
            return n;
        }

        memo[n] = (dfs(n - 1) + dfs(n - 2)) % 1000000007;
        return memo[n];
    }
};